import java.util.Arrays;

public class 链式前向星 {


    public static int MAXN = 11;//点的最大数目
    // 边的最大数量
    // 只有链式前向星方式建图需要这个数量
    // 注意如果无向图的最大数量是m条边，数量要准备m*2
    // 因为一条无向边要加两条有向边
    public static int MAXM = 21;
    //(点1,点2)
    public static int[] head = new int[MAXN];//下标为点1 存储为边
    public static int[] next = new int[MAXM];//下标为边 存储为下一条边的编号
    public static int[] to = new int[MAXM];//下标为边  存储为点2
    public static int[] weight = new int[MAXM];//下标为边 存储为该边权值
    public static int cnt;//计数器每边的编号

    // 链式前向星建立无向图带权图
    public static void undirectGraph(int[][] edges) {
        for(int[] edge : edges){
            addEdge(edge[0],edge[1],edge[2]);
            addEdge(edge[1],edge[0],edge[2]);

        }
    }

    // 三种方式建立有向图带权图
    public static void directGraph(int[][] edges) {
        for(int[] edge : edges){
            addEdge(edge[0],edge[1],edge[2]);
        }
    }

    // 链式前向星加边
    public static void addEdge(int u, int v, int w) {
        next[cnt] = head[u];
        head[u] = cnt;
        to[cnt] = v;
        weight[cnt++] = w;
    }
    // 链式前向星清空
    public static void build(int n) {
        cnt = 1;
        Arrays.fill(head,1,n + 1,0);
    }

    public static void traversal(int n) {
        for (int i = 1; i <= n; i++) {
            System.out.print(i + "(邻居、边权) : ");
            for (int j = head[i]; j != 0 ; j = next[j]) {
                System.out.print("(" + to[j] + "," + weight[j] + ") ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 理解了带权图的建立过程，也就理解了不带权图
        // 点的编号为1...n
        // 例子1自己画一下图，有向带权图，然后打印结果
        int n1 = 4;
        int[][] edges1 = { { 1, 3, 6 }, { 4, 3, 4 }, { 2, 4, 2 }, { 1, 2, 7 }, { 2, 3, 5 }, { 3, 1, 1 } };
        build(n1);
        directGraph(edges1);
        traversal(n1);
        System.out.println("==============================");
        // 例子2自己画一下图，无向带权图，然后打印结果
        int n2 = 5;
        int[][] edges2 = { { 3, 5, 4 }, { 4, 1, 1 }, { 3, 4, 2 }, { 5, 2, 4 }, { 2, 3, 7 }, { 1, 5, 5 }, { 4, 2, 6 } };
        build(n2);
        undirectGraph(edges2);
        traversal(n2);
    }
}
